// https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

// class Solution {
// public:
//     int jump(vector<int>& nums) {
//         int n = nums.size();
//         vector<int> v(n);
//         for (int i = 1; i < n; i++) {
//             v[i] = 10e5;
//         }

//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j <= nums[i]; j++) {
//                 if (i + j < n) {
//                     v[i + j] = min(v[i + j], v[i] + 1);
//                 }
//             }
//         }
//         return v[n - 1];
//     }
// };